package main.java.indi.zyj.coderecord;

import java.util.LinkedList;
import java.util.List;

public class _06_allPathsSourceTarget {

    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> trace = new LinkedList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        if(graph == null || graph.length==0){
            return res;
        }
        trace.add(0);
        dfs(graph, 0);
        return res;

    }

    private void dfs(int[][] graph, int i) {

        if (i == graph.length - 1) {
            res.add(new LinkedList<>(trace));
            return;
        }


        for (int j = 0; j < graph[i].length; j++) {
            trace.add(graph[i][j]);
            dfs(graph, graph[i][j]);
            trace.removeLast();
        }

    }
}
